1. Field of the Invention
The present invention relates to techniques of generating random numbers and, more particularly, to a circuit and a method for controlling the quality of random numbers.
2. Description of the Related Art
The internet, which continues growing rapidly, is convenient on one hand, but its security is quite uncertain on the other hand. There is an ever increasing need for highly advanced cryptographic technologies for maintaining the secrecy of communications. Cryptographic schemes currently used in general can be classified into two categories: secret-key cryptography such as DES (Data Encryption Standard) and triple DES, and public-key cryptography such as RSA (Rivest Shamir Adieman) and ECC (Elliptic Curve Cryptography). However, these are cryptographic communication methods that ensure the security of communications based on the “complexity of computation” and are always fraught with the danger that ciphertext could be broken with the advent of an algorithm enabling a vast amount of computation or a cryptanalysis algorithm. With such a background, quantum key distribution (QKD) systems receive attention as the cryptographic key distribution technologies that are “absolutely immune against eavesdropping.”
In QKD, a photon is generally used as a communication medium, and transmission is performed by superposing information on the quantum state (such as polarization and phase) of a photon. According to the Heisenberg's uncertainty principle, it is impossible to perfectly return the quantum state of a photon once observed to its original state before observation. Therefore, if an eavesdropper present on a transmission line intercepts the information by tapping photons being transmitted or by any other methods, a change occurs in the statistic values of received data detected by an authorized receiver. By monitoring this change, the receiver can detect the presence of an eavesdropper on the transmission line.
In the case of a quantum key distribution method utilizing the phase of a photon, a sender and a receiver (hereinafter, referred to as “Alice” and “Bob” respectively, as have been used traditionally) constitute an optical interferometer, and Alice and Bob individually perform random phase modulation on each of single photons. Depending on a difference between the depths of these phase modulations, an output can be obtained by a photon receiver 0 or another photon receiver 1 on Bob's side. Thereafter, Alice and Bob check part of the respective conditions they used in measurement of the output data against each other, whereby the same bit string can be shared between Alice and Bob ultimately. Hereinafter, brief description will be given of one of the most typical quantum key distribution algorithms, called BB84 protocol, which is described in Bennett and Brassard, “Quantum Cryptography: Public Key Distribution and Coin Tossing”, IEEE International Conference on Computers, Systems and Signal Processing (Bangalore, India, Dec. 10-12, 1984), pp. 175-.
FIG. 1 is a schematic diagram showing a concept of a quantum key distribution method according to the BB84 protocol. Here, it is assumed that Alice (sender) 191 and Bob (receiver) 193 are connected through an optical transmission line 192. According to this method, Alice 191 has two random number sources, one of which provides random numbers 1 representing cryptographic key data (0/1), and the other one of which provides random numbers 2 for determining the way of coding the information of the random number 1. In the case of utilizing the phase of a photon, a random number 2 determines a selection from two bases, which correspond to two coding sets: a coding set of phases of 0 and π representing “0” and “1” in the cryptographic key, respectively (hereinafter, this set will be referred to as “+ basis”); and a coding set of phases of π/2 and 3π/2 representing “0” and “1” in the cryptographic key, respectively (hereinafter, this set will be referred to as “× basis”). That is, any one of the four types of modulation (0, π/2, π, 3π/2) is randomly given to each of single photons, which are then sent to Bob one by one.
On the other hand, Bob has a random number source (random number 3) for the bases and uses the random numbers 3 to decode the single photons sent from Alice. When the value of a random number 3 is “0”, 0-phase (+ basis) modulation is performed on a photon. When the value of a random number 3 is “1”, π/2-phase (× basis) modulation is performed on a photon. Here, a random number obtained as an output of the optical interferometer is referred to as a random number 4.
When a basis Alice used in modulation is the same as a basis Bob used in modulation (random number 2=random number 3), Bob can correctly detect the value of a random number 1 (random number 1=random number 4). When a basis Alice used in modulation is different from a basis Bob used in modulation (random number 2≠random number 3), Bob randomly obtains a value “0” or “1” as a random number 4, independently of the value of a random number 1. Since each of the random numbers 1, 2 and 3 is a random number varying bit by bit, the probability that a basis match occurs and the probability that no basis match occurs are both 50%. However, since those bits corresponding to non-matching bases are removed through basis reconciliation at a subsequent stage, Alice and Bob can share a bit string composed of 0s and 1s corresponding to the random numbers 1.
FIG. 2 is a flowchart showing a flow of quantum key generation in general. Among original random numbers for a cryptographic key sent from Alice, most amount of the information is lost through quantum key distribution (single-photon transmission) S181. A key shared between Alice and Bob at this stage is called a raw key. After basis reconciliation S182, an obtained cryptographic key that has lost approximately one half the amount of information, is called a sifted key. Thereafter, error correction S183 is carried out to correct errors that have arisen in the key at the stage of quantum key distribution, followed by privacy amplification S184 for eliminating the amount of information that conceivably has been leaked to an eavesdropper. Then, the remains are made to be a final key, which will be actually used as a cryptographic key. As for a logic to estimate the amount of information that conceivably has been leaked to an eavesdropper, many a document is known to mention it, such as N. Lutkenhaus, “Estimates for practical quantum cryptography”, Physical Review A, Vol. 59, No. 5 (May 1999), pp. 3301—(hereinafter, this document will be referred to as Lutkenhaus), and M. Williamson and V. Vedral, “Eavesdropping on practical quantum cryptography”, quantum-ph/0211155 v1 (24 Nov. 2002) (hereinafter, this document will be referred to as Williamson).
FIG. 3 is a diagram for describing a privacy amplification scheme in general. First, a sifted key is divided into N-bit subsequences, and a matrix multiplication of a M-by-N random number matrix with each N-bit subsequence is performed, thus obtaining M-bit (N>M) subsequences, which are the products of this multiplication, as a final key. Here, the relationship between M bits and N bits is determined depending on the amount of information conceivably leaked to an eavesdropper, Eve. The amount of leaked information can be calculated based on the error rate of the sifted key, by a method described in Lutkenhaus or Williamson. For example, when the amount of leaked information can be estimated at 40% of the whole amount of information, it is set that M/N=1−0.4=0.6.
However, in a quantum key distribution system, in actuality, only part of a sent bit sequence arrives at the receiving side. Therefore, even if the proportions of “0”s and “1”s in the sent random numbers are precisely 50% each, the proportions of “0”s and “1”s in the received bit sequence deviate from 50%. Therefore, if a sifted key is generated based on a raw key in which the proportions of “0”s and “1”s deviate from 50%, the proportions of “0”s and “1”s in the sifted key also deviate. Hereinafter, it is assumed that a mark ratio Rm is the ratio of the number of numbers with one of the values included in random numbers to the total number of the random numbers. In the case of random numbers composed of “0”s and “1”s, the following is defined: mark ratio Rm=(the number of “1”s in a sequence of the random numbers)/(the length of the sequence of the random numbers).
In the case where the mark ratio Rm of a sifted key deviates from 50%, Eve can obtain a larger amount of information by using a simple method (mark ratio eavesdropping strategy) as follows.
Eve eavesdrops on communications performed by Alice and Bob to calculate the error rate of a sifted key, thereby obtaining knowledge about the mark ratio of the sifted key.
When the mark ratio is 50% or greater, Eve allows a cryptographic key of her own (hereinafter, referred to as false sifted key) to be all “1”s. When the mark ratio is smaller than 50%, Eve allows it to be all “0”s.
According to this operation, the probability that Eve's false sifted key matches the sifted key shared between Alice and Bob becomes higher as the mark ratio of the sifted key deviates further from 50%. By way of example, when the mark ratio of a sifted key is 60%, there are 60 bits of “1”s and 40 bits of “0”s in the 100-bit sifted key, probabilistically. In this case, since the bits in the Eve's false sifted key are all “1”s, 60 bits of the 100 bits make matches, with the error ratio of the false sifted key to the sifted key being 40%. It is known that the Shannon information S can be expressed by the following equation:S=1+E log2E+(1−E)log2(1−E)where E is the error ratio. Therefore, when the error ratio E is 40%, the Shannon information is approximately 0.03. Accordingly, of the 100 bits, information equivalent to 3 bits is leaked to Eve.
FIG. 4A is a graph showing the amount of information obtained by Eve through the mark ratio eavesdropping strategy, varying with the mark ratio of a sifted key. FIG. 4B is a part of the graph of FIG. 4A, enlarged around a mark ratio of 50%. When the mark ratio is 50%, the probability that the false sifted key matches the sifted key is 50% even if Eve allows the 100 bits in the false sifted key to be all “0”s or all “1”s (or allows “0”s and “1”s to coexist in the key with a ratio of 50% to 50%). That is to say, the error ratio is also 50%, and Eve's amount of information (S) is zero.
On the other hand, as an extreme example, when the mark ratio is 100% (or 0%), all the bits in the sifted key are “1”s (or “0”s). Therefore, Eve can correctly presume all the bits, and Eve's amount of information (S) is one.
As described above, Eve carries out eavesdropping on quantum key distribution (single-photon transmission) by using any of the eavesdropping strategies considered in Lutkenhaus and Williamson and other eavesdropping strategies such as those described in A. Acin et al., “Coherent-pulse implementations of quantum cryptography protocols resistant to photon-number-splitting attacks”, Physical Review A, No. 69, 012309 (2004), and N. Gisin et al., “Quantum cryptography”, Reviews of Modern Physics, No. 74, pp. 145-195. Eve can obtain more bit information by additionally applying the above-described mark ratio eavesdropping strategy to the bits on which Eve could not obtain information, that is, the bits about which Eve could not determine whether bit information is “0” or “1”.
However, if the above-mentioned process of privacy amplification is ideal, it is possible to maintain the safety of a final key, even if the mark ratio of a sifted key deviates from 50% as described above. Nonetheless, if an attempt to actually secure the safety is made, Alice and Bob must discard a large amount of information in the process of privacy amplification, resulting in the cryptographic key generation rate being degraded.
As is apparent from the graph of FIG. 4B, Eve's amount of information immediately rises where the mark ratio deviates from 50%. Therefore, in quantum key distribution, it is preferable that the mark ratio of random numbers before entering the process of privacy amplification be strictly 50%. For the methods by which the mark ratio of random numbers is made to be 50%, the following methods are known.
(1) Von Neumann Unbiasing Method
The Von Neumann unbiasing method is known as a general method for having the mark ratio of random numbers be 50%. According to this method, input random numbers are divided into 2-bit subsequences, among which a subsequence of “00” and a subsequence of “11” are discarded, and a subsequence of “01” and a subsequence of “10” are replaced with new numbers of “0” and “1”, respectively. Thereby, even if the mark ratio of the random numbers before the process deviates from 50%, the mark ratio of the random numbers after the process can be made to be 50%. However, according to this method, the quantity of outputs is one fourths or smaller the quantity of input random numbers. Therefore, in the case of using this method particularly in quantum key distribution, the cryptographic key generation rate is significantly degraded.
(2) Method Utilizing the Characteristics of Four-Value Signal
The major cause of the deviation of the mark ratio of a sifted key from 50% lies in a photon receiver. Therefore, it is conceivable that a mark ratio of 50% could be maintained by adjusting the photon receiver.
Specifically, the following method can also be adopted, according to the description in D. S. Bethune and W. P. Risk, “An Autocompensating Fiber-Optic Quantum Cryptography System Based on Polarization Splitting of Light”, IEEE Journal of Quantum Electronics, Vol. 36, No. 3 (March 2000) (hereinafter, this document will be referred to as Bethune). That is, the mark ratio of a cryptographic key can also be made closer to 50% by adding some refinement to the method of coding the four quantum states according to BB84, which is one of the most common protocols for quantum key distribution.
FIG. 5 is a diagram showing an outline of a mark ratio improving method based on the description in Bethune. As described above by using FIG. 1, coding is performed such that a signal will be outputted to a photon receiver 0 when “0” is sent by using the + basis, a signal will be outputted to a photon receiver 1 when “1” is sent by using the + basis, a signal will be outputted to the photon receiver 1 when “0” is sent by using the × basis, and a signal will be outputted to the photon receiver 0 when “1” is sent by using the × basis. Here, the probability of detecting each of the four quantum states can be represented as follows:P1(probability of detecting “0” with + basis)=S1(probability of generating “0” with + basis)*Q0;P2(probability of detecting “1” with + basis)=S2(probability of generating “1” with + basis)*Q1;P3(probability of detecting “0” with × basis)=S3(probability of generating “0” with × basis)*Q1;andP4(probability of detecting “1” with × basis)=S4(probability of generating “1” with × basis)*Q0,where Q0 and Q1 are the detection efficiencies of the photon receivers 0 and 1, respectively. Here, assuming that S1 to S4 are strictly equal to each other (S1=S2=S3=S4), then(probability of obtaining “0”)=P1+P3=S1*Q0+S3*Q1=(Q0+Q1)*S1, and(probability of obtaining “1”)=P2+P4=S2*Q1+S4*Q0=(Q0+Q1)*S1.Accordingly, it can be confirmed that the numbers of “0”s and “1”s in obtained random numbers are equal to each other.
However, even if the probabilities of generating the respective states (S1 to S4) are set equal to each other, they cannot be equal in actuality at the time of generating a signal, due to temporal variations in device driving conditions. Specifically, S1 to S4 are not equal to each other due to variations in the number of photons caused by a voltage noise in a light source, variations in the purity of the individual states caused by fluctuations in the voltage for driving a phase modulator, and the like. If S1 to S4 are not equal to each other, the mark ratio of generated random numbers deviates from 50%, with a need for mark ratio compensation newly arising. Specifically, to pass NIST SP800-22 as a random number test for measuring the quality of random numbers, for example, the mark ratio of 1-Mbit random numbers needs to be approximately 50%±0.13%.
Incidentally, in conventional ordinary optical communications, the light intensity is high, and communications are carried out with the error ratio of a sent signal within a range of 1*10−3 or smaller. Therefore, a sent signal almost certainly matches a received signal. Even if the mark ratio of the sent signal differs from that of the received signal, the difference is of the order of 10−3 or smaller. Moreover, in the first place, such a harm that the amount of information an eavesdropper can obtain will increase if the mark ratios of the sent and received signals are different is not envisaged in the conventional optical communications. Accordingly, the presence of an eavesdropper and eavesdropping activities are not supposed. Therefore, the problem related to the mark ratio could not have arisen.
On the other hand, in a system where the sharing of secret information is performed by using very weak light at a single-photon level, the relationship between the quality of shared random numbers and the security is an important issue as described above.